1. Field of the Invention
The present invention relates generally to network coding techniques and more specifically to network coding techniques that allow receivers to recover lost packets, particularly in multicast applications, while minimizing overhead and latency.
2. Description of the Related Art
Introduction
It is desired to have network coding techniques that allow receivers to recover lost packets while minimizing overhead and latency. In particular, the coding techniques of interest should result in lower latency and overhead than digital fountain (DF) codes. Because information must be encoded across multiple packets, this coding is to be applied to messages that consist of streams of packets. The coding techniques should have the following properties:
1) The code should allow the receiver to recover a certain number of lost packets without requiring retransmissions.
2) The code should minimize ACKs and retransmissions in a multicast application. Transmission of additional parity packets allows multiple receivers to recover lost packets, rather than retransmitting each lost packet individually.
3) The code should be systematic, so that the receiver can process correctly received data without decoding delay.
4) The encoding latency should be low, so that the transmitter can send data without waiting to accumulate a large block.
5) The initial transmission of the message should have a high code rate, so that overhead is low.
6) Packets should be encoded using a sliding window, so that the decoding delay is minimized.
The first two criteria determine the performance of the code. Most medium access control protocols incur overhead to begin a transmission but do not incur significant overhead once the transmission is in progress. The ability of the code to correct packets with minimal extra transmissions and without retransmissions is an important consideration even in unicast applications. The other criteria determine the cost to the system in overhead and delay.
Background
The current approaches for this type of network encoding are to use erasure-correcting codes to encode a message block of information packets into a stream of encoded packets so that the original message block can be recovered from any set of K received encoded packets. DF codes are the best-known class of such codes. This structure can be used to reduce the number of retransmissions required to support reliable multicast. For example, suppose a source node transmits a group of K source packets to a set of destination nodes across independent wireless links. Each destination can lose a different set of transmitted packets. Suppose that the largest number of packets lost at any destination is E. With a DF code, the source only has to transmit E new encoded packets for the destinations to recover the entire message (assuming the second set of packets is received correctly). For conventional retransmission protocols, however, the source must retransmit every packet that has been lost by any destination.
The DF encoder requires a source node to store information packets until a complete message block is obtained before transmitting the encoded packets. This leads to latency at the source while packets accumulate. If the source node encodes and transmits packets as they arrive, rather than accumulating them, packet latency would be reduced. We refer to this method of encoding as a sliding window encoder. Furthermore, the sliding window encoder generates parity so that the information in lost packets can be recovered if enough subsequent packets within the window are received correctly. This reduces latency at the decoder. The DF decoder, on the other hand, does not guarantee recovery of any particular piece of information until the entire message has been recovered. As will be disclosed below, the present invention focuses on a high-rate sliding window FEC scheme with the ability to generate additional parity for retransmissions.
Alternative Considered Approaches
Since the network code must correct missing, rather than incorrect, packets, an erasure-correction code is suitable. All of the common error-control codes can correct erasures. Because erasures do not provide soft decisions, however, the advantages of conventional trellis-based codes are minimized. Block codes, such as Reed-Solomon (RS) codes, have therefore typically been used for erasure correction in past applications. Although systematic block codes allow for the immediate transmission of data symbols, an entire block of data must be accumulated before parity symbols can be generated. Trellis-based codes, by contrast, encode data using a sliding window.
A recent solution for providing erasure correction in multicast applications has been the use of DF codes. DF codes are explained in J. W. Byers, M. Luby, and M. Mitzenmacher, “A digital fountain approach to asynchronous reliable multicast,” IEEE J. Select. Areas Commun., vol. 20, pp. 1528-1540, October 2002. These codes are rateless block codes. The systematic and parity symbols to be sent are selected from a block of data using a random distribution. The advantages of DF codes are simplicity in encoding and decoding and a lack of a fixed rate. These codes introduce latency, however, because an entire message block must be accumulated before encoding begins. DF codes are not systematic.
Other block codes may also be used for multicast applications. Several papers addressing this are referenced in the Byers et. al. reference. For example, RS codes are systematic, so information symbols may be transmitted without latency, followed by a set of parity symbols to correct packet erasures. If too many packets are lost for the decoder to recover them, additional parity packets may be transmitted with further parity symbols from the codewords. Although these codes are not sliding window codes, a message can be divided into groups of data, each of which is encoded separately. The parity symbols then depend only on a limited window of data history that covers a particular codeword. Some block codes have drawbacks compared to DF codes. RS codes, for example, have limited block sizes and require significantly more processing for encoding and decoding.
Block codes can be adapted so that data is encoded with a sliding window. (The resulting structure is theoretically equivalent to a convolutional code.) This approach will be referred to as a sliding window block (SWB) code. For example, parity symbols may be generated based on a set of the most recent information symbols. One such family of codes, maximally short (MS) codes, is defined in E. Martinian and C.-E. W. Sundberg, “Burst erasure correction codes with low decoding delay,” IEEE Trans. Inform. Theory, vol. 50, pp. 2494-2502, October 2004. The codes in the Martinian et. al. reference are designed to correct bursts of erasures. These codes do not, however, produce parity symbols suitable for multicast retransmissions. Similar constructions can generate codes for more general erasure patterns. These types of codes are systematic sliding window codes with low latency but may be complex to implement.
Convolutional codes provide fast encoding with a sliding window. Conventional convolutional decoders, however, can have large decoding delays. One method of producing packets for retransmission is to use a punctured convolutional code for the initial multicast. The punctured symbols can then be sent to correct erasures. If different receivers have lost different packets, however, different punctured symbols may be required to correct the different error paths in the decoder trellis. Maintaining the decoder trellis may also require significant processing and memory. The structure of convolutional codes is not as compatible with the desired application as the structure of block codes.
Turbo codes have been proposed for hybrid ARQ transmission protocols as illustrated in A. Banerjee, D. J. Costello Jr., and T. E. Fuja, “Performance of hybrid ARQ schemes using turbo trellis coded modulation for wireless channels,” in Proc. 2000 IEEE Wireless Commun. and Networking Conf., vol. 3, pp. 1025-1029, September 2000. Turbo codes, however, are typically used with large blocks of data. The information symbols may be transmitted immediately to reduce latency, but the number of parity symbols may be relatively large unless a high-rate turbo code is used. Turbo decoding also requires significant processing. Soft decisions must be generated by a decoder for each packet, and these decisions must be retained to process retransmissions. This approach is more suitable for augmenting the error-correction capability of individual packets rather than for recovering lost packets.